/// ------------------------------------------------------------------------------------------------------------------------------------
///
/// MIT License
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy
/// of this software and associated documentation files (the "Software"), to deal
/// in the Software without restriction, including without limitation the rights
/// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
/// copies of the Software, and to permit persons to whom the Software is
/// furnished to do so, subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in all
/// copies or substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
/// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
/// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
/// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
/// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
/// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
/// SOFTWARE.
///
/// Copyright (c) 2023 ycz. All rights reserved.
///
/// Created by ycz on 2023/1/3.
///
/// @file  y_linklist.c
///
/// @brief
///     y_linklist 具体功能实现
///
/// ------------------------------------------------------------------------------------------------------------------------------------



/// ------------------------------------------------------------------------------------------------------------------------------------
/// 头文件
/// ------------------------------------------------------------------------------------------------------------------------------------

#include "y_linklist.h"

#include <stdlib.h>
#include <string.h>
#include "y_sa.h"



/// ------------------------------------------------------------------------------------------------------------------------------------
/// 宏定义
/// ------------------------------------------------------------------------------------------------------------------------------------

#ifdef _Y_LL_H
#    define Y_MALLOC y_ll_malloc
#    define Y_FREE   y_ll_free
#else
#    define Y_MALLOC malloc
#    define Y_FREE   free
#endif



/// ------------------------------------------------------------------------------------------------------------------------------------
/// 结构体
/// ------------------------------------------------------------------------------------------------------------------------------------

/// @brief 单向链表节点结构体
typedef struct single_node {
    void               *data;
    struct single_node *next;
} SINGLE_NODE_st;

/// @brief 双向链表节点结构体
typedef struct double_node {
    void               *data;
    struct double_node *next;
    struct double_node *prev;
} DOUBLE_NODE_st;

/// @brief 链表句柄结构体
struct linklist {
    LINKLIST_TYPE_e type;      ///< 链表类型
    bool            is_cycle;  ///< 链表是否循环
    uint16_t        length;    ///< 链表长度
    union {
        SINGLE_NODE_st *single_node;  ///< 单向链表开始节点
        DOUBLE_NODE_st *double_node;  ///< 双向链表开始节点
    } start;                          ///< 链表开始节点
    union {
        SINGLE_NODE_st *single_node;  ///< 单向链表结束节点
        DOUBLE_NODE_st *double_node;  ///< 双向链表结束节点
    } end;                            ///< 链表结束节点
    uint16_t end_index;               ///< 链表结束节点位置
};



/// ------------------------------------------------------------------------------------------------------------------------------------
/// 私有函数
/// ------------------------------------------------------------------------------------------------------------------------------------

/// @brief   创建一个单向节点
/// @param   [in] node_data              链表数据指针
/// @param   [in] data_size              链表数据大小
/// @return  单向节点结构体指针
static SINGLE_NODE_st *_y_linklist_create_single_node(void *node_data, uint16_t data_size) {

    // 创建单向链表节点
    SINGLE_NODE_st *tmp_node = (SINGLE_NODE_st *) Y_MALLOC(sizeof(SINGLE_NODE_st));
    if (tmp_node == NULL) {
        YLOGE("y_ll_malloc node error");
        return NULL;
    }
    tmp_node->data = Y_MALLOC(data_size);
    if (tmp_node->data == NULL) {
        YLOGE("y_ll_malloc node error");
        return NULL;
    }

    memcpy(tmp_node->data, node_data, data_size);
    tmp_node->next = NULL;

    return tmp_node;
}

/// @brief   创建一个双向节点
/// @param   [in] node_data              链表数据指针
/// @param   [in] data_size              链表数据大小
/// @return  双向节点结构体指针
static DOUBLE_NODE_st *_y_linklist_create_double_node(void *node_data, uint16_t data_size) {

    // 创建单向链表节点
    DOUBLE_NODE_st *tmp_node = (DOUBLE_NODE_st *) Y_MALLOC(sizeof(DOUBLE_NODE_st));
    if (tmp_node == NULL) {
        YLOGE("y_ll_malloc node error");
        return NULL;
    }
    tmp_node->data = Y_MALLOC(data_size);
    if (tmp_node->data == NULL) {
        YLOGE("y_ll_malloc node error");
        return NULL;
    }

    memcpy(tmp_node->data, node_data, data_size);
    tmp_node->next = NULL;
    tmp_node->prev = NULL;

    return tmp_node;
}

/// @brief   查找一个单向节点
/// @param   [in] linklist               链表句柄
/// @param   [in] index                  要查找的位置索引
/// @return  单向节点结构体指针
static SINGLE_NODE_st *_y_linklist_find_single_node(LINKLIST_st *linklist, uint16_t index) {

    // 遍历查找
    SINGLE_NODE_st *iterator_node = linklist->start.single_node;
    for (uint16_t i = 0; i < index; ++i) {
        iterator_node = iterator_node->next;  // 每次后移一个节点
    }

    return iterator_node;
}

/// @brief   查找一个双向节点
/// @param   [in] linklist               链表句柄
/// @param   [in] index                  要查找的位置索引
/// @return  双向节点结构体指针
static DOUBLE_NODE_st *_y_linklist_find_double_node(LINKLIST_st *linklist, uint16_t index) {

    // 遍历查找
    DOUBLE_NODE_st *iterator_node = NULL;
    if (index < linklist->end_index / 2) {
        // 从前往后找
        iterator_node = linklist->start.double_node;
        for (uint16_t i = 0; i < index; ++i) {
            iterator_node = iterator_node->next;  // 每次后移一个节点
        }
    } else {
        // 从后往前找
        iterator_node = linklist->end.double_node;
        for (uint32_t i = index + 1; i < linklist->end_index; ++i) {
            iterator_node = iterator_node->prev;  // 每次前移一个节点
        }
    }

    return iterator_node;
}

/// @brief   删除一个单向节点
/// @param   [in] linklist               链表句柄
/// @param   [in] index                  要删除的位置索引
/// @retval  true                        成功
/// @retval  false                       失败
static bool _y_linklist_delete_single_node(LINKLIST_st *linklist, uint16_t index) {

    SINGLE_NODE_st *delete_node = NULL;
    if (linklist->end_index == 1) {
        // 只有一个节点
        delete_node                 = linklist->start.single_node;
        linklist->start.single_node = NULL;
        linklist->end.single_node   = NULL;
    } else {
        // 不只一个节点
        if (index == 0) {
            // 删除头节点
            delete_node                 = linklist->start.single_node;
            linklist->start.single_node = linklist->start.single_node->next;
            if (linklist->is_cycle == true) {
                linklist->end.single_node->next = linklist->start.single_node;  // 循环链表 尾指向头
            }
        } else if (index == linklist->end_index - 1) {
            // 删除尾节点
            delete_node               = linklist->end.single_node;
            linklist->end.single_node = _y_linklist_find_single_node(linklist, index - 1);
            if (linklist->is_cycle == true) {
                linklist->end.single_node->next = linklist->start.single_node;
            }
        } else {
            // 删除其他节点
            SINGLE_NODE_st *tmp_node = _y_linklist_find_single_node(linklist, index - 1);  // 要删除节点的前一个节点
            delete_node              = tmp_node->next;
            tmp_node->next           = delete_node->next;
        }
    }

    Y_FREE(delete_node->data);
    delete_node->data = NULL;
    Y_FREE(delete_node);
    delete_node = NULL;
    linklist->end_index--;

    return true;
}

/// @brief   删除一个双向节点
/// @param   [in] linklist               链表句柄
/// @param   [in] index                  要删除的位置索引
/// @retval  true                        成功
/// @retval  false                       失败
static bool _y_linklist_delete_double_node(LINKLIST_st *linklist, uint16_t index) {

    DOUBLE_NODE_st *delete_node = NULL;
    if (linklist->end_index == 1) {
        // 只有一个节点
        delete_node                 = linklist->start.double_node;
        linklist->start.double_node = NULL;
        linklist->end.double_node   = NULL;
    } else {
        // 不只一个节点
        if (index == 0) {
            // 删除头节点
            delete_node                 = linklist->start.double_node;
            linklist->start.double_node = linklist->start.double_node->next;
            if (linklist->is_cycle == true) {
                linklist->start.double_node->prev = linklist->end.double_node;
                linklist->end.double_node->next   = linklist->start.double_node;
            }
        } else if (index == linklist->end_index - 1) {
            // 删除尾节点
            delete_node               = linklist->end.double_node;
            linklist->end.double_node = linklist->end.double_node->prev;
            if (linklist->is_cycle == true) {
                linklist->start.double_node->prev = linklist->end.double_node;
                linklist->end.double_node->next   = linklist->start.double_node;
            }
        } else {
            // 删除其他节点
            delete_node             = _y_linklist_find_double_node(linklist, index);
            delete_node->prev->next = delete_node->next;
            delete_node->next->prev = delete_node->prev;
        }
    }

    Y_FREE(delete_node->data);
    delete_node->data = NULL;
    Y_FREE(delete_node);
    delete_node = NULL;
    linklist->end_index--;

    return true;
}



/// ------------------------------------------------------------------------------------------------------------------------------------
/// 公有函数
/// ------------------------------------------------------------------------------------------------------------------------------------

/// @brief 打印 y_linklist 版本号
void y_linklist_print_version() {
    YLOG_VERSION("y_linklist", Y_LINKLIST_MAJOR, Y_LINKLIST_MINOR, Y_LINKLIST_PATCH);
}

/// @brief   打印所有节点数据的地址
/// @param   [in] linklist               链表句柄
void y_linklist_print_data_addr(LINKLIST_st *linklist) {

    // 断言
    if (linklist == NULL) {
        YLOGE("linklist is NULL");
        return;
    }

    for (uint16_t i = 0; i < linklist->end_index; ++i) {
        YLOGD("index %d  data addr is %p", i, y_linklist_find(linklist, i));
    }
}

/// @brief   获取节点总数量
/// @param   [in] linklist               链表句柄
/// @return  节点总数量
uint16_t y_linklist_get_num(LINKLIST_st *linklist) {

    // 断言
    if (linklist == NULL) {
        YLOGE("linklist is NULL");
        return 0;
    }

    return linklist->end_index;
}

/// @brief   查找一个节点数据的位置
/// @param   [in] linklist               链表句柄
/// @param   [in] node_data              要查找的数据指针
/// @param   [in] data_size              要查找的数据大小
/// @return  成功 : 节点数据所在的索引位置    失败 : -1
int16_t y_linklist_find_index(LINKLIST_st *linklist, void *node_data, uint16_t data_size) {

    // 断言
    if (linklist == NULL) {
        YLOGE("linklist is NULL");
        return -1;
    }
    if (node_data == NULL) {
        YLOGE("node_data is NULL");
        return -1;
    }
    if (data_size == 0) {
        YLOGE("data_size is 0");
        return -1;
    }

    // 根据类型查找节点
    if (linklist->type == SINGLE_LINKLIST) {
        // 遍历查找
        for (int16_t i = 0; i < (int16_t) linklist->end_index; ++i) {
            if (memcmp(_y_linklist_find_single_node(linklist, i)->data, node_data, data_size) == 0) {
                return i;
            }
        }
    } else if (linklist->type == DOUBLE_LINKLIST) {
        // 遍历查找
        for (int16_t i = 0; i < (int16_t) linklist->end_index; ++i) {
            if (memcmp(_y_linklist_find_double_node(linklist, i)->data, node_data, data_size) == 0) {
                return i;
            }
        }
    }

    return -1;
}

/// @brief   查找一个节点的数据
/// @param   [in] linklist               链表句柄
/// @param   [in] index                  要查找的位置索引
/// @return  [out] node_data             节点数据指针
void *y_linklist_find(LINKLIST_st *linklist, uint16_t index) {

    // 断言
    if (linklist == NULL) {
        YLOGE("linklist is NULL");
        return NULL;
    }
    if (index >= linklist->end_index) {
        YLOGE("index error ");
        return NULL;
    }

    // 根据类型查找节点
    if (linklist->type == SINGLE_LINKLIST) {
        return _y_linklist_find_single_node(linklist, index)->data;  // 查找单向链表中的节点
    } else if (linklist->type == DOUBLE_LINKLIST) {
        return _y_linklist_find_double_node(linklist, index)->data;  // 查找双向链表中的节点
    }

    return NULL;
}

/// @brief   插入一个节点 取代当前索引节点
/// @param   [in] linklist               链表句柄
/// @param   [in] index                  要插入的位置索引
/// @param   [in] node_data              要插入的数据指针
/// @param   [in] data_size              要插入的数据大小
/// @retval  true                        成功
/// @retval  false                       失败
bool y_linklist_insert(LINKLIST_st *linklist, uint16_t index, void *node_data, uint16_t data_size) {

    // 断言
    if (linklist == NULL) {
        YLOGE("linklist is NULL");
        return false;
    }
    if (node_data == NULL) {
        YLOGE("node_data is NULL");
        return false;
    }
    if (data_size == 0) {
        YLOGE("data_size is 0");
        return false;
    }
    if (linklist->end_index >= linklist->length) {
        YLOGE("linklist is full");
        return false;
    }
    if (index > linklist->end_index) {
        YLOGE("insert index error ");
        return false;
    }

    // 根据类型插入节点
    if (linklist->type == SINGLE_LINKLIST) {

        // 创建单向链表节点
        SINGLE_NODE_st *tmp_node = _y_linklist_create_single_node(node_data, data_size);
        if (tmp_node == NULL) {
            return false;
        }
        // 判断链表中有没有节点
        if (linklist->end_index == 0) {
            // 没有节点
            linklist->end.single_node   = tmp_node;
            linklist->start.single_node = tmp_node;
            if (linklist->is_cycle == true) {
                linklist->end.single_node->next = linklist->start.single_node;  // 循环链表 尾指向头
            }
        } else {
            // 有节点
            if (index == 0) {
                // 头部插入
                tmp_node->next              = linklist->start.single_node;
                linklist->start.single_node = tmp_node;
                if (linklist->is_cycle == true) {
                    linklist->end.single_node->next = linklist->start.single_node;  // 循环链表 尾指向头
                }
            } else if (index == linklist->end_index) {
                // 尾部追加
                tmp_node->next                  = linklist->end.single_node->next;
                linklist->end.single_node->next = tmp_node;
                linklist->end.single_node       = tmp_node;
            } else {
                // 其他地方插入
                SINGLE_NODE_st *prev_insert_node = _y_linklist_find_single_node(linklist, index - 1);
                tmp_node->next                   = prev_insert_node->next;
                prev_insert_node->next           = tmp_node;
            }
        }

    } else if (linklist->type == DOUBLE_LINKLIST) {

        // 创建双向链表节点
        DOUBLE_NODE_st *tmp_node = _y_linklist_create_double_node(node_data, data_size);
        if (tmp_node == NULL) {
            return false;
        }
        // 判断链表中有没有节点
        if (linklist->end_index == 0) {
            // 没有节点
            linklist->end.double_node   = tmp_node;
            linklist->start.double_node = tmp_node;
        } else {
            // 有节点
            if (index == 0) {
                // 头部插入
                tmp_node->next                    = linklist->start.double_node;
                linklist->start.double_node->prev = tmp_node;
                linklist->start.double_node       = tmp_node;
            } else if (index == linklist->end_index) {
                // 尾部追加
                tmp_node->prev                  = linklist->end.double_node;
                linklist->end.double_node->next = tmp_node;
                linklist->end.double_node       = tmp_node;
            } else {
                // 其他地方插入
                DOUBLE_NODE_st *prev_insert_node = _y_linklist_find_double_node(linklist, index - 1);
                prev_insert_node->next->prev     = tmp_node;
                tmp_node->next                   = prev_insert_node->next;
                prev_insert_node->next           = tmp_node;
                tmp_node->prev                   = prev_insert_node;
            }
        }
        // 判断是否是循环链表
        if (linklist->is_cycle == true) {
            linklist->end.double_node->next   = linklist->start.double_node;  // 循环链表 尾指向头
            linklist->start.double_node->prev = linklist->end.double_node;    // 循环链表 头也指向尾
        }
    }

    linklist->end_index++;  // 总节点数加一
    return true;
}

/// @brief   添加一个节点 在尾部
/// @param   [in] linklist               链表句柄
/// @param   [in] node_data              要添加的数据指针
/// @param   [in] data_size              要添加的数据大小
/// @retval  true                        成功
/// @retval  false                       失败
bool y_linklist_add(LINKLIST_st *linklist, void *node_data, uint16_t data_size) {

    // 断言
    if (linklist == NULL) {
        YLOGE("linklist is NULL");
        return false;
    }

    return y_linklist_insert(linklist, linklist->end_index, node_data, data_size);  // 插入尾部
}

/// @brief   删除一个节点
/// @param   [in] linklist               链表句柄
/// @param   [in] index                  要删除的位置索引
/// @retval  true                        成功
/// @retval  false                       失败
bool y_linklist_delete(LINKLIST_st *linklist, uint16_t index) {

    // 断言
    if (linklist == NULL) {
        YLOGE("linklist is NULL");
        return false;
    }
    if (index >= linklist->end_index) {
        YLOGE("delete index error ");
        return false;
    }

    // 根据类型删除节点
    if (linklist->type == SINGLE_LINKLIST) {
        return _y_linklist_delete_single_node(linklist, index);
    } else if (linklist->type == DOUBLE_LINKLIST) {
        return _y_linklist_delete_double_node(linklist, index);
    }

    return false;
}

/// @brief   删除所有节点
/// @param   [in] linklist               链表句柄
/// @retval  true                        成功
/// @retval  false                       失败
bool y_linklist_delete_all(LINKLIST_st *linklist) {

    // 断言
    if (linklist == NULL) {
        YLOGE("linklist is NULL");
        return false;
    }

    // 根据类型遍历删除所有节点
    uint16_t tmp_size = linklist->end_index;
    if (linklist->type == SINGLE_LINKLIST) {
        for (uint16_t i = 0; i < tmp_size; ++i) {
            _y_linklist_delete_single_node(linklist, 0);
        }
    } else if (linklist->type == DOUBLE_LINKLIST) {
        for (uint16_t i = 0; i < tmp_size; ++i) {
            _y_linklist_delete_double_node(linklist, 0);
        }
    }

    return true;
}

/// @brief   判断链表是否为满
/// @param   [in] linklist               链表句柄
/// @retval  true                        成功
/// @retval  false                       失败
bool y_linklist_is_full(LINKLIST_st *linklist) {

    // 断言
    if (linklist == NULL) {
        YLOGE("linklist is NULL");
        return false;
    }

    if (linklist->end_index == linklist->length) {
        return true;
    } else {
        return false;
    }
}

/// @brief   判断链表是否为空
/// @param   [in] linklist               链表句柄
/// @retval  true                        成功
/// @retval  false                       失败
bool y_linklist_is_empty(LINKLIST_st *linklist) {

    // 断言
    if (linklist == NULL) {
        YLOGE("linklist is NULL");
        return false;
    }

    if (linklist->end_index == 0) {
        return true;
    } else {
        return false;
    }
}

/// @brief   销毁一个链表
/// @param   [in] linklist               链表句柄
/// @retval  true                        成功
/// @retval  false                       失败
bool y_linklist_destroy(LINKLIST_st *linklist) {

    // 断言
    if (linklist == NULL) {
        YLOGW("linklist is NULL, no need destroy");
        return false;
    }

    // 删除所有节点
    y_linklist_delete_all(linklist);

    Y_FREE(linklist);
    YLOGD("linklist %p destroy succeed", linklist);
    linklist = NULL;

    return true;
}

/// @brief   创建一个链表
/// @param   [in]  linklist_type         链表类型
/// @param   [in]  is_cycle              链表是否循环
/// @param   [in]  length                链表长度
/// @return  链表句柄指针
LINKLIST_st *y_linklist_create(LINKLIST_TYPE_e linklist_type, bool is_cycle, uint16_t length) {

    // 断言
    if (length == 0) {
        YLOGE("linklist length must > 0, linklist create fail");
        return NULL;
    }
    if (linklist_type != SINGLE_LINKLIST && linklist_type != DOUBLE_LINKLIST) {
        YLOGE("linklist_type error, linklist create fail");
        return NULL;
    }

    // 创建 linklist 句柄
    LINKLIST_st *linklist = (LINKLIST_st *) Y_MALLOC(sizeof(LINKLIST_st));  // 开辟 结构体句柄 所需要的空间;
    if (linklist == NULL) {
        YLOGE("y_ll_malloc LINKLIST_st error");
        return NULL;
    } else {
        memset(linklist, 0, sizeof(LINKLIST_st));  // 清零
    }

    // 初始化
    linklist->type      = linklist_type;
    linklist->is_cycle  = is_cycle;
    linklist->length    = length;
    linklist->end_index = 0;

    YLOGD("linklist %p create succeed", linklist);
    return linklist;
}
